遞迴（Recursion）

遞迴是一種程式設計的概念，它通過函式自己呼叫自己來解決問題。它是一種強大的技巧，可以將複雜的問題分解成較小、更易管理的子問題。通過遞迴解決每個子問題，最終可以達到不需要進一步遞迴的基本情況。

遞迴的過程涉及將一個問題分解為相同問題的較小實例，並個別解決它們。然後將這些較小的實例結合起來獲得原始問題的最終解。這種方法對於解決具有重複結構的問題特別有用。

在程式設計中，遞迴通常用於與樹的遍歷、圖的遍歷和分治策略相關的演算法。它提供了一種優雅而簡潔的方法來解決某些類型的問題，但在決定使用遞迴之前，必須仔細分析問題並考慮其他替代方案。

題目：206. Reverse Linked List

連結：https://leetcode.com/problems/reverse-linked-list/description/

• 等級：Easy

解題思路

1. 先考慮單一Node反轉．
2. 遞迴重複執行

class Solution {
    private ListNode rev(ListNode current,ListNode prev)
    {
        if (current == null) return prev;
        ListNode temp = current.next;
        current.next = prev;
        return rev(temp,current);
    }
    public ListNode reverseList(ListNode head) {
            return rev(head,null);
    }
}

• Time complexity: O(n)
• Space complexity: O(1)

題目：24. Swap Nodes in Pairs

連結：https://leetcode.com/problems/reverse-linked-list/description/

• 等級：Medium

解題思路

1. 2個一組進行對換
2. 遞迴重複執行

class Solution {

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode temp = head.next;
        head.next = swapPairs(head.next.next);
        temp.next = head;
        return temp;
    }
}

• Time complexity: O(n)
• Space complexity: O(n)